//
//  main.c
//  C_Study
//
//  Created by rui on 12-9-2
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//



/*
 *查找
 */

#include "types.h"

#pragma mark helper
void printArray(int *arr,int length){
	for (int i=0; i<length; i++) {
		printf("%d ",arr[i]);
	}
	printf("\n");
}


#pragma mark - Search

/*
 *二分查找
 */

int BinSearch(int *arr,int length,int searchNum)
{
	int low=0,high=length-1,mid;
	while (low<=high) {
		mid = (low+high)/2;
		if (arr[mid]==searchNum) {
			return searchNum;
		}
		else if (arr[mid]>searchNum) {
			low = mid+1;
		}
		else {
			high = mid-1;
		}
	}
	
	return 0;//表示未找到
}


/*
 *分块查找
 */

typedef struct heap {
	int low;
	int high;
	int key;
}Heap;//一个块


typedef struct statictable{
	Heap heap[4];
	int data[20];
}STable;//建立有块的表

int SerchHeap(STable *a,int searchNum)
{
	//用数组记录有序的块号
	int key[4];
	for (int i=0; i<4; i++) {
		key[i] = (a->heap[i]).key;
	}
	
	//先找到块号(二分查找)
	int heapIndex=0;
	int low=0,high=3,mid;
	
	while (low<=high) {
		mid = (low+high)/2;
		if (searchNum <= key[mid]) {
			high = mid-1;
		}
		else {
			low = mid+1;
		}
	}
	heapIndex = high+1;//结束循环时low=high，此时指向的块为要找的块为high+1
	
	if (heapIndex>3 || heapIndex<0) {
		return 0;
	}
	
	//在相应的块号里查找
	int searchLow = (a->heap[heapIndex]).low;
	int searchHigh = (a->heap[heapIndex]).high;
	
	while (searchLow <= searchHigh) {
		if (a->data[searchLow]==searchNum) {
			return searchNum;
		}
		else {
			searchLow++;
		}
	}
	
	return 0;
}

/*
 分块验证代码
 STable t;
 
 for (int i=0; i<20; i++) {
 t.data[i] = i;
 }
 
 Heap h1 = {0,5,5};
 Heap h2 = {6,10,10};
 Heap h3 = {11,16,16};
 Heap h4 = {17,19,19};
 t.heap[0] = h1;
 t.heap[1] = h2;
 t.heap[2] = h3;
 t.heap[3] = h4;
 
 printf("%d\n",SerchHeap(&t,3));
*/
/*-------------------------------------------------------------------------------------------------------------------------*/


/*
 *树表查找
 */
typedef struct binode {
	struct binode *lchild;
	struct binode *rchild;
	int data;
}BiNode,*BiTree;


void insertBiNode(BiTree T,int val)
{
	BiTree p = (BiTree)malloc(sizeof(BiNode));
	p->data = val;
	p->lchild = p->rchild = NULL;
	
	BiTree q = T;
	BiTree rec = T; //记录插入节点的父节点位置
	
	//寻找插入点
	while (NULL!=q) {
		if (p->data >= q->data) {
			rec = q;
			q = q->rchild;
		}
		else {
			rec = q;
			q = q->lchild;
		}
	}
	
	//插入
	if (p->data >= rec->data) {
		rec->rchild = p;
	}
	else {
		rec->lchild = p;
	}
}

//更普通的造树不一样，这个要根据顺序来造
void creatBiTree(BiTree *pTree,int arr[],int length)
{	
	*pTree = (BiTree)malloc(sizeof(BiNode));
	(*pTree)->data = arr[0];
	(*pTree)->lchild = (*pTree)->rchild = NULL;
	
	for (int i=1; i<length; i++) {
		insertBiNode(*pTree,arr[i]);
	}
}

void in_traveal(BiTree t)
{
	if (t!=NULL) {
		in_traveal(t->lchild);
		printf("%d ",t->data);
		in_traveal(t->rchild);
	}
}

int TreeSearch(BiTree t,int seachNum)
{
	
	if (NULL == t)
		return 0;
	
	int ret;
	if (t->data == seachNum) {
		return seachNum;
	}
	else if(seachNum>t->data){
		ret = TreeSearch(t->rchild, seachNum);
	}
	else {
		ret = TreeSearch(t->lchild, seachNum);
	}
	
	return ret;
}

/*
 树表查找验证代码
 BiTree T = NULL;
 int a[] = {19,13,35,21,88,56,27,3,80,7,13};
 creatBiTree(&T,a,11);
 in_traveal(T);
 printf("\n");
 printf("%d\n",TreeSearch(T,80));
 */
/*-------------------------------------------------------------------------------------------------------------------------*/


/*
 *哈希查找(冲突是由hash函数产生的,是在查找时产生的)
 */

typedef struct
{
	int key;
	int data;
}ElemType; /* 数据元素类型 */


typedef struct
{
	ElemType *elem; /* 数据元素存储基址，动态分配数组 */
	int count; /* 当前数据元素个数 */
}HashTable;


#define NULLKEY 0

void initHashTable(HashTable *H,ElemType arr[],int length)
{
#define MAXSIZE 50
	ElemType *p = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
	H->elem = p;
	H->count = length;
	
	for (int i=0; i<length; i++) {
		H->elem[i] = arr[i];
	}
}

/* 一个简单的哈希函数*/
int Hash(HashTable *H,int K)
{ 
	return K%(H->count);
}

void collision(HashTable *H,int *p,int d) /*开放定址法处理冲突,线性探测再散列 */
{ 
	*p=(*p+d)%(H->count);
}

#define UNSUCCESS 0
#define SUCCESS 1
Status SearchHash(HashTable *H,int K,int *p)
{
	*p = Hash(H,K);
	int d = 0;
	
	while(H->elem[*p].key!=NULLKEY && K!= H->elem[*p].key)/* 该位置中填有记录．并且关键字不相等 */
	{ 
		d++;
		if(d < H->count)
			collision(H,p,d); /* 求得下一探查地址p */
		else
			break;
	}
	
	if(K == H->elem[*p].key){/* 查找成功，p返回待查数据元素位置 */
		return SUCCESS; 
	}
	else
		return UNSUCCESS; 
}

/**********************************/                    
 #pragma mark - Main函数
/**********************************/
int main(int argc, const char * argv[])
{
	HashTable h;
	ElemType r[10]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
	initHashTable(&h,r,10);
	
	int p;
	
	if (SearchHash(&h, 13, &p)) {
		printf("%d\n",h.elem[p].data);
	}

	return 0;
}

